package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * @author feizns
 * @since 2020/3/9
 */
public class BuildTree2 {

    public static void main(String[] args) {
        final TreeNode node = buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println(node);
    }

    static int pL;

    public static TreeNode buildTree(int[] inOrder, int[] postOrder) {
        pL = postOrder.length - 1;
        return buildTree(inOrder, postOrder, 0, postOrder.length - 1);
    }

    private static TreeNode buildTree(int[] inOrder, int[] postOrder, int l, int r) {
        TreeNode root = null;
        if ( l == r )
            root = new TreeNode(postOrder[pL--]);
        else if ( l < r ) {
            root = new TreeNode(postOrder[pL--]);
            int i = l;
            for(; i <= r && inOrder[i] != root.val; i++) { }
            root.right = buildTree(inOrder, postOrder, i + 1, r);
            root.left = buildTree(inOrder, postOrder, l, i - 1);
        }
        return root;
    }

}
